class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size() == 0)
        	return 0;
        int index1 = 0;
        int index2 = rotateArray.size()-1;
        int mid = index1;
        while(rotateArray[index1] >= rotateArray[index2])
        {
        	if(index2 - index1 == 1)
        		return rotateArray[index2];
        	mid = (index1+index2)/2;
        	if(rotateArray[index1]==rotateArray[mid] && rotateArray[index2] == rotateArray[mid])
        		return findLiner(vector<int>(rotateArray.begin()+index1,rotateArray.begin() + index2+1));
        	if(rotateArray[mid] >= rotateArray[index1])
        		index1 = mid;
        	else if(rotateArray[mid]<= rotateArray[index2])
        		index2 = mid;
        }
    	return rotateArray[mid];
    }
    int findLiner(vector<int> rotateArray)
    {
    	int idx = rotateArray.size()-1;
    	int min = rotateArray[idx];
    	while(idx >=0 )
    	{
    		if(min < rotateArray[idx])
    			min = rotateArray[idx];
    		--idx;
    	}
    	return min;
    }
};